package com.company.algo.niuke;

import com.company.algo.pojo.ListNode;

/**【做过又出错了】
  链表中环的入口结点
  快慢指针，fast一次前进两步，slow一次前进一步
  当fast和slow第一次相遇，说明有环，将fast重新移到head，并让slow和fast每次都前进一步
  第二次相遇的位置记为环的入口
 */
public class CircleListNodeEntry {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode fast = pHead,slow = pHead;
        do{
            if (fast == null || fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
        }while (fast!=slow);
        fast = pHead;
        while (fast!=slow){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}
